High five [Heap]

Time: O(NLogN); Space: O(N); easy

Given a list of scores of different students, return the average score of each student’s top five scores in the order of each student’s id.

Each entry items[i] has items[i][0] the student’s id, and items[i][1] the student’s score.

The average score is calculated using integer division.

Example 1:

Input: items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]

Output: [[1,87], [2,88]]

Explanation:

  • The average of the student with id = 1 is 87.

  • The average of the student with id = 2 is 88.6. But with integer division their average converts to 88.

Example 2:

Input: items =

[
    [1,46],[1,44],[1,92],[1,26],[1,90],
    [2, 7],[2,76],[2,20],[2,46],[2,68],
    [3, 8],[3,55],[3,66],[3,55],[3,62],
    [4,22],[4,90],[4,92],[4,13],[4,89],
    [5,13],[5,20],[5,82],[5,83],[5,25],
    [6,83],[6,89],[6,33],[6,16],[6,70],
    [7,85],[7,15],[7,33],[7,72],[7, 9]

]

Output: [[1,59], [2,43], [3,49], [4,61], [5,44], [6,58], [7,42]]

Constraints:

  • 1 <= len(items) <= 1000

  • items[i].length == 2

  • The IDs of the students is between 1 to 1000

  • The score of the students is between 1 to 100

  • For each student, there are at least 5 scores

1. Using Heap

[1]:

import collections
import heapq

class Solution1(object):
    """
    Time:  O(NLogN)
    Space: O(N)
    """
    def highFive(self, items):
        """
        :type items: List[List[int]]
        :rtype: List[List[int]]
        """
        min_heaps = collections.defaultdict(list)

        for i, val in items:
            heapq.heappush(min_heaps[i], val)
            if len(min_heaps[i]) > 5:
                heapq.heappop(min_heaps[i])

        return [[i, sum(min_heaps[i]) // len(min_heaps[i])] for i in sorted(min_heaps)]

[2]:

s = Solution1()
items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
assert s.highFive(items) == [[1,87],[2,88]]

items = [[1,46],[1,44],[1,92],[1,26],[1,90],
         [2, 7],[2,76],[2,20],[2,46],[2,68],
         [3, 8],[3,55],[3,66],[3,55],[3,62],
         [4,22],[4,90],[4,92],[4,13],[4,89],
         [5,13],[5,20],[5,82],[5,83],[5,25],
         [6,83],[6,89],[6,33],[6,16],[6,70],
         [7,85],[7,15],[7,33],[7,72],[7, 9]
]
assert s.highFive(items) == [[1,59], [2,43], [3,49], [4,61], [5,44], [6,58], [7,42]]